package binary;

import java.util.Objects;

/**
 * 二分查找
 * https://mp.weixin.qq.com/s/1ExIav9uK4bvVnnf4t0H2Q
 *
 * @auther yang
 * @date 2022/3/17 9:47
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};
        int target = 5;
        System.out.println(binarySearch(a, target));
        System.out.println(binSearch(a, target));
    }

    public static int binarySearch(int[] a, int target) {
        if (Objects.isNull(a) || a.length < 1) return -1;
        return search(a, target);
    }

    public static int binSearch(int[] a, int target) {
        if (Objects.isNull(a) || a.length < 1) return -1;
        return search(a, target, 0, a.length - 1);
    }

    // ========================================================================
    //  二分查找的递归写法
    // ========================================================================

    private static int search(int[] a, int target, int lo, int hi) {
        if (lo > hi) return -1;
        int mid = lo + ((hi - lo) >> 1);
        if (a[mid] == target) return mid;
        else if (a[mid] < target) return search(a, target, mid + 1, hi);
        else return search(a, target, lo, mid - 1);
    }

    // ========================================================================
    //  二分查找的非递归写法
    // ========================================================================

    private static int search(int[] a, int target) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            if (a[mid] == target) return mid;
            else if (a[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

}
